/**
 * 
 */
package com.gragra.clustering;
import java.util.Iterator;
import it.unimi.dsi.fastutil.ints.Int2ObjectMap.Entry;
import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
import com.gragra.data.MixingCorpus;
import com.gragra.distances.Mean;
import com.gragra.distances.MeanFactory;
import com.gragra.sampling.ThreadedUniformAccess;
import com.gragra.sampling.vector.VectorStructure;
/**
 * a simple implementation of K-Means-Clustering, note that it requires that the data to be clusters
 * contains at least as many datapoints as there are clusters
 * @author Christoph Teichmann
 * created Apr 30, 2013 2:23:27 PM
 * @version 0.1
 */
public class KMeansClusterer implements ClusteringAlgorithm
{
	/**
	 * the number of clusters used
	 */
	private final int clusterNumber;
	/**
	 * the maximum number of iterations used
	 */
	private final int maxIterations;
	/**
	 * constructs a new instance that can take do an arbitrary number of iterations
	 * @param fact
	 */
	public KMeansClusterer(MeanFactory fact, int clusterNumber)
	{this(fact, -1, clusterNumber);}
	/**
	 * creates a new instance, 0 or less for maxIterations indicates that the algorithm can take as many iterations
	 * as it needs
	 * @param fact
	 */
	public KMeansClusterer(MeanFactory fact, int maxIterations, int clusterNumber)
	{
		if(clusterNumber <= 1)
		{throw new IllegalArgumentException("K-Means Clustering is pointless when k<2");}
		this.fact = fact;
		this.maxIterations = maxIterations;
		this.clusterNumber = clusterNumber;
	}
	@Override
	public void cluster(MixingCorpus<? extends VectorStructure> data, ThreadedUniformAccess tua)
	{
		if(data.size() < this.clusterNumber)
		{
			throw new IllegalArgumentException("there are less VectorStructures in the data then there are clusters");
		}
		int iterations = 0;
		this.means.clear();
		data.mix(tua,0);
		Iterator<? extends VectorStructure> vit = data.mixingIterator();
		for(int i=0;i<clusterNumber;++i)
		{
			Mean m = fact.createInstance();
			m.add(vit.next());
			m.set();
			this.means.put(i, m);
		}
		while(this.changed && (iterations < this.maxIterations || this.maxIterations <= 0))
		{
			this.changed = false;
			this.meansConstr.clear();
			for(int i=0;i<this.clusterNumber;++i)
			{this.meansConstr.put(i, this.fact.createInstance());}
			this.redoMeans(data,tua);
			this.means.clear();
			vit = null;
			for(Mean m : this.meansConstr.values())
			{
				if(m.empty())
				{
					if(vit == null)
					{
						data.mix(tua,0);
						vit = data.mixingIterator();
					}
					m.add(vit.next());
				}
				m.set();
			}
			this.means.putAll(meansConstr);
			++iterations;
			System.out.println("finished one k-means iteration");
		}
	}
	/**
	 * reassigns the VectorStructures to clusters and informs the clusters that are under construction of the
	 * respective assignments
	 * @param data
	 */
	private void redoMeans(MixingCorpus<? extends VectorStructure> data, ThreadedUniformAccess tua)
	{
		for(VectorStructure vs : data)
		{
			int oldNumber = -1;
			if(this.assignments.containsKey(vs))
			{oldNumber = this.assignments.getInt(vs);}
			int bestCluster = -1;
			double leastCluster = Double.POSITIVE_INFINITY;
			Iterator<Entry<Mean>> it = this.means.int2ObjectEntrySet().fastIterator();
			while(it.hasNext())
			{
				Entry<Mean> ent = it.next();
				Mean m = ent.getValue();
				double val = m.getDistance(vs);
				// so values don't just get assigned to the first cluster in the map that fits well,
				// especially relevant if vector does not fit with any cluster, so there is no clear 'dump' cluster
				if(val == leastCluster && tua.nextBoolean(0))
				{

					bestCluster = ent.getIntKey();
					leastCluster = val;
				}
				else if(val < leastCluster)
				{
					bestCluster = ent.getIntKey();
					leastCluster = val;
				}
			}
			if(oldNumber != bestCluster)
			{
				this.assignments.put(vs, bestCluster);
				this.changed = true;
			}
			this.meansConstr.get(bestCluster).add(vs);
		}
	}
	/**
	 * contains the current assignments from VectorStructures to cluster numbers
	 */
	private final Object2IntOpenHashMap<VectorStructure> assignments = new Object2IntOpenHashMap<VectorStructure>();
	/**
	 * indicates whether the assignments have changed during the last iteration
	 */
	private boolean changed  = true;
	/**
	 * contains the means currently under construction
	 */
	private final Int2ObjectOpenHashMap<Mean> meansConstr = new Int2ObjectOpenHashMap<Mean>();
	/**
	 * contains the means that are currently being used for clustering
	 */
	private final Int2ObjectOpenHashMap<Mean> means = new Int2ObjectOpenHashMap<Mean>();
	/**
	 * contains the factory used to produce more means
	 */
	private final MeanFactory fact;
	@Override
	public int getBest(VectorStructure vs, int number)
	{return this.assignments.getInt(vs);}	
}